#ifndef LEFTIST_HEAP
#define LEFTIST_HEAP
#include"Node.h"
#include <iostream>
using namespace std;

class Lheap{

public:
	Lheap() :root(0){}
	~Lheap(){ makeEmpty(); }

	Lheap(const Lheap & rhs)
	{
		*this = rhs;
	}

	Lheap & operator= (const Lheap & rhs)
	{
		makeEmpty();
		root = clone(rhs.root);
		return *this;
	}

	inline void insert(int x)
	{
		root = merge(new Node(0, 0, x), root);
	}

	void deleteMin(int * i)
	{
		if (root == 0)
			return;
		*i = root->element;
		root = merge(root->right, root->left);
	}

	void merge(const Lheap & rhs)
	{
		//clone first!
		Node * rhsroot = clone(rhs.root);
		root = merge(root, rhsroot);
	}

	void makeEmpty()
	{
		makeEmpty(root);
	}
	
	inline void desc()
	{
		desc(root);
	}

	

private:
	
	Node * merge(Node * h1, Node * h2); //base1 and compare
	Node * merge1(Node* h1, Node * h2); //base2 and traverse


	inline void desc(Node * t)
	{
		if (t == 0)
			return;
		
		desc(t->left);
		cout << t->element << endl;
		desc(t->right);
	}

	Node * root;

	void swapChildren(Node * t);

	void makeEmpty(Node *& root);


	Node * clone( Node *t) const 
	{
		if (t == 0)
			return 0;
		return new Node(clone(t->left), clone(t->right), t->element, t->npl);
	}
};




#endif
